package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/">从前序与中序遍历序列构造二叉树 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-28 16:19
 */
public class ConstructBinaryTreeFromPreorderAndInorderTraversal_105 {

  public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> inMap = new HashMap<>(); // 构建存放中序遍历的元素与对应的位置，方便查询
    for (int i = 0; i < inorder.length; i++) {
      inMap.put(inorder[i], i);
    }
    return buildTree(0, 0, inorder.length - 1, preorder, inMap);
  }

  /**
   * @param preStart 先序遍历中的开始位置
   * @param inStart  中序遍历中的开始位置
   * @param inEnd    中序遍历中的结束位置
   * @param preorder 先序遍历
   * @param inMap    中序遍历的值与对应的位置map
   * @return root节点
   */
  public TreeNode buildTree(int preStart, int inStart, int inEnd, int[] preorder, Map<Integer, Integer> inMap) {
    if (preStart > preorder.length - 1 || inStart > inEnd) {
      return null;
    }

    TreeNode root = new TreeNode(preorder[preStart]); // 构建当前的根节点
    int rootOfInIndex = inMap.get(root.val); // 获取root在中根遍历数组中所在的位置


    /*当前根节点的左节点就是先序遍历的下一个位置，还是根，然后从中根遍历起始开始直到找到了根节点在中序遍历中出现的位置-1，即寻找范围是所有左侧*/
    root.left = buildTree(preStart + 1, inStart, rootOfInIndex - 1, preorder, inMap); // 递归构建左侧所有节点
    /*根节点的右节点在先序遍历的开始位置就是先序当前root在中序的位置左侧一共有多少个节点，从先序root节点跳过这些节点就是下一个根*/
    root.right = buildTree(preStart + (rootOfInIndex - inStart) + 1, rootOfInIndex + 1, inEnd, preorder, inMap); // 递归构建右侧所有节点

    return root;
  }
}
